//
// Created by liushuai on 12/19/19.
//
#include <unordered_map>

std::unordered_map<int, int> cache;

int climbStairs(int n) {
    if (cache.count(n))
        return cache.at(n);
    else {
        if (n < 3)
            return n;
        else {
            int result = 0;
            result = climbStairs(n - 1) + climbStairs(n - 2);
            cache[n] = result;
            return result;
        }

    }
}

int climbStairs(int n, int m) {
    if (n >= m)
        return 0;
    else if (n == m)
        return 1;
    else
        return climbStairs(n + 1, m) + climbStairs(n + 2, m);
}
